package org.gushi.graph.a01;

import java.util.*;

public class ListGraph<V, E> implements Graph<V, E> {

    private Map<V, Vertex<V, E>> vertices = new HashMap<>();
    private Set<Edge<E>> edges = new HashSet<>();

    public void print() {
        vertices.forEach((V v, Vertex<V, E> vertex) -> {

            System.out.println(v);
            System.out.println("out-------------------");
            System.out.println(vertex.outEdges);
            System.out.println("in-------------------");
            System.out.println(vertex.inEdges);


        });

        edges.forEach((Edge<E> edge)->{
            System.out.println(edge);
        });
    }

    @Override
    public int edgesSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertices.size();
    }

    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) {
            return;
        }
        vertices.put(v, new Vertex<>(v));
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {

        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }
        Edge<E> edge = new Edge<>(fromVertex, toVertex, weight);
        edge.weight = weight;

        if (fromVertex.inEdges.remove(edge)) {
            toVertex.outEdges.remove(edge);
            edges.remove(edge);
        }

        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);

        edges.add(edge);

    }

    @Override
    public void removeVertex(V v) {
        Vertex<V, E> vertex = vertices.get(v);
        if (vertex == null) {
            return;
        }
        vertices.remove(v);

        for (Iterator<Edge<E>> it = vertex.outEdges.iterator();it.hasNext();) {
            Edge<E> edge = it.next();
//            vertex.outEdges.remove(edge);
            edge.to.inEdges.remove(edge);
            it.remove();
            edges.remove(edge);
        }

        for (Iterator<Edge<E>> it = vertex.inEdges.iterator();it.hasNext();) {
            Edge<E> edge = it.next();
//            vertex.inEdges.remove(edge);
            edge.from.outEdges.remove(edge);
            it.remove();
            edges.remove(edge);
        }

    }

    @Override
    public void removeEdge(V from, V to) {

        Vertex<V, E> vertexFrom = vertices.get(from);
        Vertex<V, E> vertexTo = vertices.get(to);
        if (vertexFrom == null || vertexTo == null) {
            return;
        }

        Edge<E> edge = new Edge<>(vertexFrom, vertexTo);
        vertexFrom.outEdges.remove(edge);
        vertexTo.inEdges.remove(edge);
        edges.remove(edge);


    }

    /**
     * 广度优先遍历
     * @param begin
     */
    @Override
    public void bfs(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) {
            return;
        }

        Queue<Vertex<V, E>> queue = new LinkedList<>();
        //记录已经遍历的节点
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        queue.offer(beginVertex);

        while (queue.size() > 0) {
            Vertex<V, E> vertex = queue.poll();
            System.out.println(vertex.element);
            if(vertex.outEdges!=null && vertex.outEdges.size()>0){
                for (Edge<E> edge:vertex.outEdges){
                    if(visitedVertices.contains(edge.to)){
                        continue;
                    }
                    queue.offer(edge.to);
                    visitedVertices.add(edge.to);
                }
            }
        }

    }
    /**
     * 深度优先遍历 【非递归的方式实现】
     * @param begin
     */
    @Override
    public void dfs(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) {
            return;
        }
        //记录已经遍历的节点
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();
        stack.push(beginVertex);
        System.out.print(beginVertex.element+",");
        visitedVertices.add(beginVertex);


        while (!stack.isEmpty()){
            Vertex<V, E> vertex = stack.pop();

            if (vertex.outEdges == null || vertex.outEdges.size() <= 0) {
                continue;
            }
            for (Edge<E> edge: vertex.outEdges){
                if(visitedVertices.contains(edge.to)){
                    continue;
                }
                stack.push(edge.from);
                stack.push(edge.to);
                visitedVertices.add(edge.to);
                System.out.print(edge.to.element+",");
                break;
            }

        }

    }

//    /**
//     * 深度优先遍历
//     * @param begin
//     */
//    @Override
//    public void dfs(V begin) {
//        Vertex<V, E> beginVertex = vertices.get(begin);
//        if (beginVertex == null) {
//            return;
//        }
//        //记录已经遍历的节点
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//        dfs(beginVertex,visitedVertices);
//    }
//
//    /**
//     * 递归的方式实现深度优先遍历
//     * @param vertex
//     * @param visitedVertices
//     */
//    private void dfs(Vertex<V, E> vertex,Set<Vertex<V, E>> visitedVertices){
//        System.out.println(vertex.element);
//        visitedVertices.add(vertex);
//        if (vertex.outEdges == null || vertex.outEdges.size() <= 0) {
//            return;
//        }
//        for (Edge<E> edge:vertex.outEdges) {
//            if(visitedVertices.contains(edge.to)){
//                continue;
//            }
//            dfs(edge.to,visitedVertices);
//        }
//
//    }

    //定义图的顶点
    private static class Vertex<V, E> {
        V element;

        Set<Edge<E>> inEdges = new HashSet<>();//其他顶点的到此定点的边，以此this顶点为终点的边，代表入度
        Set<Edge<E>> outEdges = new HashSet<>();
        ;//以此顶点到其他定点的边，以此this顶点为起始的边，代表出度


        public Vertex(V element, Set<Edge<E>> inEdges, Set<Edge<E>> outEdges) {
            this.element = element;
            this.inEdges = inEdges;
            this.outEdges = outEdges;
        }

        public Vertex(V element) {
            this.element = element;
        }

        public Vertex() {
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex<?, ?> vertex = (Vertex<?, ?>) o;
            return Objects.equals(element, vertex.element);
        }

        @Override
        public int hashCode() {

            return element == null ? 0 : element.hashCode();
        }

        @Override
        public String toString() {

            String elementStr = element == null ? "null" : element.toString();

            return "Vertex{" +
                    "element=" + elementStr +
//                    ", inEdges=" + inEdges +
//                    ", outEdges=" + outEdges +
                    '}';
        }

    }

    //定义图的边
    private static class Edge<E> {
        Vertex from; //边的起点
        Vertex to;//边的尾巴

        E weight;//边的权值

        public Edge(Vertex from, Vertex to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Edge(Vertex from, Vertex to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
//            if (this == o) return true;
//            if (o == null || getClass() != o.getClass()) return false;
            Edge<?> edge = (Edge<?>) o;
            return Objects.equals(from, edge.from) &&
                    Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            int fromCode = from.hashCode();
            int toCode = to.hashCode();

            return fromCode * 31 + toCode;
        }
    }

}
